Masala #0476

Xotira 16 MB Vaqt 1000 ms Qiyinchiligi 50 %

3.0 (Baholar 5)

Permutatsiyalar soni №3

$A$ ketma-ketlik 1 dan $N$ gacha bo'lgan sonlarning shunday permutatsiyasiki unda $A_1 = 1, |A_i - A_{i-1}| < 3, (2 \le i \le n)$ bo'ladi. Sizga $N$ soni beriladi, $A$ ketma -ketlikni hosil qilish variantlar sonini aniqlang!

Kiruvchi ma'lumotlar:

Kirish faylida yagona butun son, $N (1 \le N \le 10^{18})$ soni kiritiladi

Chiquvchi ma'lumotlar:

Chiqish faylida yagona butun son, so’ralgan natijaning $1000000007 (10^9+7)$ ga bo’lgandagi qoldiqni chop eting.

Misollar

#	input.txt	output.txt
1	3	2
2	4	4

Telegram Facebook

Yechimini yuborish

Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin